package dynamicProgramming.baseKnowledge;

/**
 * @author zxc
 * @date 2023/01/18 11:56
 **/
/**
 * 题目 ：爬楼梯的最少成本
 * 题目详述 ：
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值cost[i]（下标从 0 开始）。
 * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
 * 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 *
 * 提示：
 * 2 <= cost.length <= 1000
 * 0 <= cost[i] <= 999
 */
public class MinCostClimbingStairs_newIteration {
    /**
     * 思路 ：迭代（即，从子问题开始解决，同时保存子问题解的结果，合并子问题解的结果，从而解决大问题）
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        /**
         * 相比于之前的迭代代码，唯一区别在于 ：所创建的辅助数组的大小;
         * （1）之前的迭代代码 ：
         * 所创建的辅助数组大小为n，存储的是 从每级台阶（index）继续向上爬所需要的最少成本;
         * ===> 通俗易懂来说，辅助数组所存储的是 到该台阶所需要的最少成本 + 该台阶继续向上爬所需要的成本;
         * （2）改进之后的迭代的吗 ：
         * 核心 ：为求取f(i)的结果，只需要使用辅助数组来存储f(i-1)和f(i-2);
         * ===》 即，代表了辅助缓存数组的大小只需要保证为2即可;
         */
        int[] redis = new int[]{cost[0] , cost[1]};
        for(int i = 2 ; i < length ; i++){
            // 由于所要去求解的是f(i),只需要保证redis辅助缓存数组中所存储的是，f(i-1)和f(i-2);
            redis[i % 2] = Math.min(redis[0] , redis[1]) + cost[i];
        }
        return Math.min(redis[0] , redis[1]);
    }
}
